package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/11/29 9:25
 * @description：https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/
 */
public class 第K个最小的素数分数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.kthSmallestPrimeFraction(new int[]{1, 2, 3, 5}, 3)));
    }

    /*
    class Solution {
        public int[] kthSmallestPrimeFraction(int[] arr, int k) {
            ArrayList<int[]> doubles = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    double num = (double) arr[i] / (double) arr[j];
                    doubles.add(new int[]{arr[i], arr[j]});
                }
            }
            doubles.sort((Comparator<int[]>) (x, y) -> {
                // x[0] / x[1] = y[0] / y[1]
                return x[0] * y[1] - x[1] * y[0];
            });
            return doubles.get(k - 1);
        }
    }
    */

    // 优先队列
    class Solution {
        public int[] kthSmallestPrimeFraction(int[] arr, int k) {
            PriorityQueue<int[]> queue =
                    new PriorityQueue<>((x, y) -> x[0] * y[1] - x[1] * y[0]);

            int len = arr.length;
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j < len; j++) {
                    queue.offer(new int[]{arr[i], arr[j]});
                }
            }
            for (int i = 0; i < k - 1; i++) {
                queue.poll();
            }
            return queue.poll();
        }
    }

}
